package com.kclm.se.sort;

import java.util.Arrays;

/****
 * @author yejf
 * @since JDK8.0
 * @CreateDate 2020年12月3日 上午10:10:15 
 * @description 此类用来描述了排序算法
 *
 */
public class SortAlgorithm {

	/***********
	 * 冒泡排序算法
	 * @param arr
	 */
	public static void bubbleSort(int[] arr) {
		if(arr == null) {
			return ;
		}
		//只负责循环轮次的控制
		for(int i = 0;i < arr.length-1; i++) {
			//
			System.out.printf("\n第[%d]轮:", i+1);
			// 负责交换相邻
			for(int j = 0; j < arr.length - 1; j++) {
				//相邻的两个元素比较，把小的往前移
				if(arr[j] > arr[j+1]) {
					System.out.print("交换   ");
					//交换
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
	
	/***********
	 * 选择排序
	 * 由外层循环控制次数，每次从外层循环中“拿出”一个元素，就认为此元素是“最小”的，然后，在内层循环中
	 * 去比较，如果有比这个假定的元素还小的，就交换
	 * @param arr
	 */
	public static void selectionSort(int[] arr) {
		if(arr == null) {
			return ;
		}
		//定义一个变量来存保当前最小元素的下标
		int min_index = -1, temp;
		//
		for(int i = 0; i < arr.length-1; i++) {
			//假设当前的i位置处的元素就是最小的
			min_index = i;
			//
			System.out.printf("\n第【%d】轮：", i+1);
			//
			for(int j = i+1; j < arr.length; j++) {
				//此处一定是与 arr[min_index] 比较，不能与 arr[i]比较
				if(arr[j] < arr[min_index]) {
					min_index = j;
				}
			}
			//判断
			if(i != min_index) {
				System.out.print("交换  ");
				//交换
				temp = arr[i];
				arr[i] = arr[min_index];
				arr[min_index] = temp;
			}
		}
	}
	
	/*****************
	 * 插入排序: 
	 * 假定最左边0个元素是已经排序的，然后，依次从右边取出一个元素，插入到左边，在插入的过程中，就要
	 * 确定插入的位置，保证有序
	 * @param arr
	 */
	public static void insertionSort(int[] arr) {
		if(arr == null) {
			return ;
		}
		int temp;
		//假定第一个元素[下标为0的元素]是排好序的，再依次从后面的元素中取出元素插入到有序列表中
		for(int i = 0; i < arr.length; i++) {
			System.out.printf("\n已插入[%d]个, 结果：%s\n", i, Arrays.toString(arr));
			//通过内层循环来插入元素
			for(int j = i; j > 0; j--) {
				//如果后面的元素比前面的小，则依次插入，直到后面的元素不比前面的小为止
				if(arr[j] < arr[j-1]) {
					System.out.print("交换  ");
					//
					temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
				} else {
					//如果后面的元素比前面的大了，则直接退出内层循环
					System.out.print("无需交换 ");
					break;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {5,1,2,77,34,9,11,243,90,23,10,6};
		//
		System.out.printf("排序前：%s\n", Arrays.toString(arr));
		//bubbleSort(arr);
		//selectionSort(arr);
		insertionSort(arr);
		System.out.printf("\n排序后：%s\n", Arrays.toString(arr));
	}
}
